1. Field of the Invention
Example embodiments of the present application relate generally to an apparatus for performing a fault detection operation and methods thereof, and more particularly to an apparatus for performing a fault detection operation within a cryptography system and methods thereof.
2. Description of the Related Art
Conventional encryption methods may include public key-based encrypting methods, such as the Rivest Shamir Adleman (RSA) encrypting system and the Elliptic Curve Cryptography (ECC) system. Conventional public key-based encrypting methods may use a relatively large integer as a public key to protect a system because an algorithm for integral division may not be defined.
In particular, the ECC system may provide security with a relatively small key size, and thus ECC systems may be implemented within smart cards and electronic signatures. The ECC system may include a cryptographic process for encrypting/decrypting information, based on a specific addition which is defined by a numerical formula referred to as an “elliptic curve”.
A conventional ECC system may include a random elliptic curve E, and a point P on the elliptic curve E, as system parameters. For example, a first user who desires to establish a cryptographic communication may randomly generate an integer k, and may multiply the integer k by P to obtain Q(=k×P). The first user may disclose Q as a public key, and may securely store the integer k as his/her secret key. Then, a second user who desires to transmit a message M to the first user in a secret manner may randomly generate an integer d, and may multiply d by P to obtain A(=d×P). The second user may generate B(=M+d×Q) by using the public key Q that the first user provides and the message M to be transmitted. The second user may then transmit a cryptograph A,B to the first user.
In the conventional ECC system, the first user who receives the cryptogram A,B from the second user may computes k×A based on his/her secret key k, and may restore the message M by:M=B−(k×A)  Equation 1
In order to “attack” or hack the conventional ECC system, a Differential Fault Analysis (DFA) may determine the secret key for a cryptographic system based on the difference between variables used in a given operation. In the DFA, the secret key for the cryptographic system may be determined by injecting a fault into a cryptographic system, and analyzing the result of operation corresponding to the injected fault.
For example, the conventional ECC system may use values stored in a register when performing a given operation. However, the value stored in the register, or scheduled to be stored in the register, may be adjusted or altered by the fault. Thus, an error corresponding to the altered value may affect the result of the given operation. Information relating to the secret key may thereby inadvertently be disclosed based on an analysis of the result of the given operation containing the error.
FIG. 1 is a flowchart illustrating a Calculate Twice and Check (CT&C) process 100 corresponding to a conventional DFA countermeasure. In the CT&C process 100, a random point P on an elliptic curve may be selected (at S110), a first comparison value Q1 may be computed by multiplying P by k (at S120) and a second comparison value Q2 may be computed by multiplying P by k (at S130), where k may be an integer value of a secret key.
Referring to FIG. 1, the first comparison result Q1 and the second comparison result Q2 may be compared (at S140). If the first comparison result Q1 and the second comparison result Q2 are equal to each other, a fault or error is determined not to have occurred, and one of the first comparison result Q1 and the second comparison result Q2 may be output as the result Q (at S150). Alternatively, if the first comparison result Q1 is determined not to be equal to the second comparison result Q2, a fault or error is determined to have occurred, and a warning signal may be output instead of the result Q (at S160).
FIG. 2 is a flowchart illustrating a Check the Output Point (COP) process 200 corresponding to another conventional DFA countermeasure. In the conventional COP process 200 of FIG. 2, a random point P on an elliptic curve may be selected (at S210), and a comparison value Q may be computed by multiplying P by a given integer k (at S220). The given integer k may denote a secret key.
Referring to FIG. 2, a determination is made as to whether the comparison value Q is a point on the elliptic curve E (at S230). If the comparison value Q is a point on the elliptic curve E, a fault or error is determined not to have occurred, and the result or comparison value Q may be output (at S240). Alternatively, if the comparison value Q is determined not to be a point on the elliptic curve E, an error or fault is determined to have occurred, and a warning signal may be output instead of the result or comparison value Q (at S250).
Referring to FIGS. 1 and 2, the CT&C process 100 of FIG. 1 may require a duplicate multiplication of the comparison values Q1 and Q2, which may waste system resources. The COP process 200 of FIG. 2 may be more simplistic with regard to the computations involved as compared to the CT&C process 100 of FIG. 1. However, the COP process 200 may be relatively limited and the performance thereof may not be sufficient in certain situations, such as during a fault sign changes attack. Accordingly, a Montgomery Power Ladder Algorithm (MPLA) and/or a Fast Montgomery Power Ladder Algorithm (FMPLA) may be deployed in addition to the conventional process of FIG. 1 and/or 2 to handle the DFA.
In a conventional ECC system, a discrete logarithm operation may be performed to compute k based on P and Q. The discrete logarithm operation may be performed by applying the characteristics of an elliptic curve to finite fields, and may be a basis of the cryptographic protocol. Thus, the discrete logarithm operation may refer to an operation of computing k by using Q and P in a formula Q=k×P.
Accordingly, it will be appreciated that scalar multiplication may be representative of one operation performed during a conventional ECC process. In an example, the MPLA may constitute a portion of the scalar multiplication in finite fields. The conventional MPLA will now be described in greater detail.
The MPLA may include two variables defined as shown in Equation 2, below:
                              L          j                =                                            ∑                              i                =                j                                            t                -                1                                      ⁢                                          k                i                            ⁢                              2                                  i                  -                  j                                            ⁢                                                          ⁢                              H                j                                              =                                    L              j                        +            1                                              Equation        ⁢                                  ⁢        2            wherein k may denote a random integer expressed as a plurality of binary bits (e.g., k=(kt−1, . . . , k1, k0)2), t may denote an integer, and ki may denote an ith bit of k, wherein i may denote an integer. For example, kt−1 may be equal to a first logic level (e.g., a higher logic level or logic “1”) or a second logic level (e.g., a lower logic level or logic “0”).
The relationship between Lj and Hj (e.g., expressions 1 and 2, respectively) may be expressed by:Lj=2Lj+1+kj=Lj+1+Hj+1+kj−1=2Hj+1+kj−2  Equation 3and may be alternatively expressed by:
                              (                                    L              j                        ,                          H              j                                )                =                  {                                                                                                                                        (                                                                              2                            ⁢                                                          L                                                              j                                +                                1                                                                                                              ,                                                                                    L                                                              j                                +                                1                                                                                      +                                                          H                                                              j                                +                                1                                                                                                                                    )                                            ⁢                                                                                          ⁢                      if                      ⁢                                                                                          ⁢                                              k                        j                                                              =                    0                                    ,                                                                                                                                                (                                                                                                    L                                                          j                              +                              1                                                                                +                                                      H                                                          j                              +                              1                                                                                                      ,                                                  2                          ⁢                                                      H                                                          j                              +                              1                                                                                                                          )                                        ⁢                                                                                  ⁢                    if                    ⁢                                                                                  ⁢                                          k                      j                                                        =                  1.                                                                                        Equation        ⁢                                  ⁢        4            
A process of deriving Equation 4 is well-known to those of ordinary skill in the art, and as such a detailed description thereof has been omitted for the sake of brevity. Lj and Hj may be mapped to two points P1 and P2, respectively, on an elliptic curve in the ECC system of FIG. 3, which will now be described in greater detail.
FIG. 3 is a flowchart illustrating a MPLA process 300 for performing the scalar multiplication within a conventional ECC system. In the MPLA process of FIG. 3, a basic point P and a scalar k may be received (e.g., wherein k may be an integer) (at S301). Next, variables may be set for scalar multiplication (at S303). For example, the scalar k may be set as expressed in Equation 2, a first variable P1 may be set to the basic point P, a second variable P2 may be set to the twice that of the basic point P (e.g., 2×P) and a repetitive parameter or counter i may be set or reset to t−1.
Referring to FIG. 3, after setting the variables, the scalar multiplication Q=k×P may be computed by performing a repetitive operation. Thus, the counter i may be decremented (at S305) and the process 300 may determine whether a binary bit ki is equal to 1 (at S307). The first and second variables P1 and P2 may be updated according to the determination result (at S310 or S311). In S310 and S311, “P2←2P2” and “P1←2P1” may denote a “double” operation (e.g., multiplying by two) of elliptic curve points. In S310 and S311, “P1←P1+P2” and “P2←P1+P2” may denote an addition of elliptic curve points (e.g., the values on the right side of the arrow are added together with the result being stored in the variable indicated on the left side). A determination may then be made as to whether i is less than zero (at S313). If i is not less than zero, the process 300 returns to S305 where i is decremented and the repetitive portion of the process 300 repeats. Otherwise, if i is less than zero, the first variable P1 may be output as the scalar multiplication Q=k×P (at S315).
Referring to FIG. 3, both the addition and the double operation may be performed for each iteration or repetition of the process 300 (e.g., S305, S307, S310 or S311, and S313), which may degrade system performance. A level of system resource allocation to the process 300 may be reduced with scalar multiplication in which a Y-axis is redefined after loop computation excluding Y-axis computation.
To perform the double operation and the addition on P1(X1,Z1) and P2(X2,Z2), with P1 and P2 representing points (e.g., having an X-axis component and a Z-axis component, respectively) on an elliptic curve using the FMPLA, the double operation and the addition in the binary finite field may be respectively defined as follows:
                    {                                                            Z                =                                                      Z                    i                    2                                    ·                                      X                    i                    2                                                                                                                          X                =                                                      X                    i                    4                                    +                                      b                    ·                                          Z                      i                      4                                                                                                                              Equation        ⁢                                  ⁢        5                                {                                                                              Z                  3                                =                                                      (                                                                                            X                          1                                                ·                                                  Z                          2                                                                    +                                                                        X                          2                                                ·                                                  Z                          1                                                                                      )                                    2                                                                                                                          X                  3                                =                                                      x                    ·                                          Z                      3                                                        +                                                            (                                                                        X                          1                                                ·                                                  Z                          2                                                                    )                                        ·                                          (                                                                        X                          2                                                ·                                                  Z                          1                                                                    )                                                                                                                              Equation        ⁢                                  ⁢        6            
In Equations 5 and 6 (above), a Y-axis may not be included within P1 and P2. In Equation 6, it may be assumed that the difference between the Z-axis coordinates of the difference between two points P1(X1,Z1) and P2(X2,Z2) (e.g., ZD=Z2−Z1) may be “1”. However, in a fault detecting process used in the FMPLA, this assumption may not necessarily be true. Accordingly, if the addition in Equation 6 is applied to the fault detecting process using the FMPLA, the ECC system may not accurately determine whether a fault or error is injected into the system, which may degrade performance of the ECC system.